//
// Created by Administrator on 2021/5/26.
//

//给定一棵二叉搜索树，请找出其中第k大的节点。

#include <iostream>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int kthLargest(TreeNode *root, int k) {
        // 中序遍历为递增 找到倒数第k个
        vector<int> v;
        dfs(root, v);
        return v[v.size()-k];
    }

    void dfs(TreeNode *root, vector<int> &v) {
        // 中序遍历
        if (root == nullptr) return ;
        dfs(root->left, v);
        v.push_back(root->val);
        dfs(root->right, v);
    }
};
class Solution2 {
    int maxSize=0;
public:

    int kthLargest(TreeNode *root, int k) {
        // 中序遍历的倒序为递减 找到第k个
        this->maxSize = k;
        vector<int> v;
        dfs(root, v);
        return v.back();
    }

    bool dfs(TreeNode *root, vector<int> &v) {
        // 中序遍历 的倒序
        // 先右后左
        if (root == nullptr) return false ;
        if (dfs(root->right, v)) return true;
        v.push_back(root->val);
        if (v.size() == this->maxSize) return true;
        if (dfs(root->left, v)) return true;
        return false;
    }
};
int main() {
    auto n1 = TreeNode(3), n2 = TreeNode(1), n3 = TreeNode(4), n4 = TreeNode(2);
    n1.left = &n2;
    n1.right = &n3;
    n2.right = &n4;
    Solution2 sol;
    cout << sol.kthLargest(&n1, 1) << endl;
    return 0;
}